// 有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值?
// 要求时间和空间复杂度尽可能低

//无序数组: 2 6 3 4 5 10 9
//排序结果: 2 3 4 5 6 9 10
//最大相邻差  3

// 1. 先排序，然后求出任意两个相邻元素的最大差值

//1.利用桶排序的思想，根据原数组的长度n，创建出n个桶，每一个桶代表一个区间范围。
//  其中第1个桶从原数组的最小值min开始，区间跨度是（max-min）/(n-1)
//2.遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大和最小值
//3.遍历所有的桶，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差
//  即为原数组排序后的相邻最大的差值

function getMaxSortedDistance(array){
  //1. 得到数列的最大值和最小值
  let max = array[0];
  let min = array[0];
  for(let i=1;i<array.length;i++){
     if(array[i]>max){
        max=array[i];
     }
     if(array[i]<min){
        min = array[i];
     }
  }
  let d=max-min;
  //如果max 和 min 相等，说明数组所有的元素都相等，返回0
  if(d==0){
    return 0;
  }
  // 2. 初始化桶
  let bucketNum = array.length;
  let buckets = new Array(bucketNum);
  for(let i=0;i<bucketNum;i++){
    buckets[i]=new Bucket();
  }

  // 3.遍历原始数组，确定每个桶的最大最小值
  for(let i=0;i<array.length;i++){
    // 确定数组元素所属的下标
    let index = Math.floor((array[i]-min)*(bucketNum-1)/d);
    console.log(index);
    if(buckets[index].min==null || buckets[index].min>array[i]){
        buckets[index].min = array[i];
    }
    if(buckets[index].max==null || buckets[index].max<array[i]){
        buckets[index].max = array[i];
    }
  }
  //4. 遍历桶，找到最大差值

  //存储当前左侧桶的最大值
  let leftMax = buckets[0].max;
  
  let maxDistance = 0;
  for(let i =1;i<buckets.length;i++){
      if(buckets[i].min == null){
        continue;
      }
      if(buckets[i].min - leftMax > maxDistance){
        maxDistance = buckets[i].min - leftMax
      }
      leftMax = buckets[i].max;
  }
  return maxDistance;
}

class Bucket{
    constructor(){
        this.min=null;
        this.max=null;
    }
}

let array = [2,6,3,4,5,10,9]
console.log(getMaxSortedDistance(array))